package com.zh.note.huawei.twohundred.数据最节约的备份方法;

import java.util.Arrays;
import java.util.Scanner;

/**
 * https://dream.blog.csdn.net/article/details/131232368
 */
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String inputStr = sc.nextLine();
        int[] files = Arrays.stream(inputStr.split(",")).mapToInt(Integer::parseInt).toArray();
        Arrays.sort(files);

        int left = 0;
        int right = files.length + 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (canAllocate(files, mid)) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }

        }
        System.out.println(left);

    }

    // 创建k个光盘判断是否够存储
    private static boolean canAllocate(int[] files, int k) {

        int[] boxCapacities = new int[k];
        Arrays.fill(boxCapacities, 500);
        for (int i = files.length - 1; i >= 0; i--) {
            int file = files[i];
            Arrays.sort(boxCapacities);
            if (boxCapacities[k - 1] >= file) {
                boxCapacities[k - 1] -= file;
            } else {
                return false;
            }
        }
        return true;
    }
}
